/**
 * \file Graphe.cpp
 * \brief Implémentation d'un graphe orienté où chaque sommet un nom.
 * \author Pierre-Marc Levasseur, Simon Rodier
 * \version 0.1
 * \date juillet 2014
 *
 *  Travail pratique numéro 3
 *
 */

#include "Graphe.h"
#include <math.h>

using namespace std;

namespace TP3
{
	/*
	 * \fn Graphe::Graphe()
	 */
	Graphe::Graphe()
	:nbSommets(0), nbArcs(0)
	{
		listeSommets = NULL;
	}

	/*
	 * \fn Graphe::~Graphe
	 */
	Graphe::~Graphe()
	{
		detruireGraphe();
	}

	/**
	 *  \fn appel de la méthode
	 *  \param[in] paramètre d'entrée
	 *  \param[out] paramètre de sortie
	 *  \return ce que la méthode retourne
	 */
	Graphe::Graphe(const Graphe &source)
	{
		try
		{
			_copieListeSommets(source.listeSommets, source.nbSommets, source.nbArcs);
		}
		catch (bad_alloc& ba)
		{
			throw ba;
		}
	}

	/**
	 *  \fn Graphe::operator=(const Graphe& src)
	 *  \param[in] src, un graphe à copier
	 *  \return un graphe qui est copie profonde de src
	 */
	Graphe& Graphe::operator=(const Graphe& src)
	{
		try
		{
			//vérifier que ce n'est pas exactement le même graphe
			if ( listeSommets == src.listeSommets)
			{
				return *this;
			}
			else //si ça ne l'est pas, faire la copie.
			{
				//si src est null, on renvoit un graphe vide
				detruireGraphe();
				//notre graphe est maintenant vide.  si le graphe src est vide, tout est beau.  sinon, on fait la copie.
				if(src.listeSommets!=NULL)
				{
					_copieListeSommets(src.listeSommets, src.nbSommets, src.nbArcs);
				}
			}
		}
		catch (bad_alloc& ba)
		{
			throw ba;
		}
		return *this;
	}

	/*
	 * \fn Graphe::ajouterSommet(const string&, float, float)
	 *
	 * \param[in] nom: nom du sommet qu'on veut ajouter
	 * \param[in] lt: latitude du sommet
	 * \param[in] lg: longitude du sommet
	 */
	void Graphe::ajouterSommet(const string& nom, float lt, float lg)
	{
		if(sommetExiste(nom))
			throw logic_error("ajouterSommet: le sommet existe déjà dans le graphe.");

		Coordonnees coord;
		coord.lg = lg;
		coord.lt = lt;
		// pointeur temporaire sur le sommet qu'on veut ajouter
		Sommet* nouveauSommet = new Sommet(nom, coord);
		// si c'est le premier noeud qu'on ajoute à la chaîne
		if(nbSommets == 0)
		{
			listeSommets = nouveauSommet;
			nbSommets++;
			return;
		}
		// sinon on se place un noeud avant le dernier et on fait l'insertion
		Sommet* temp = listeSommets;
		while(temp->suivant != NULL)
		{
			temp = temp->suivant;
		}
		temp->suivant = nouveauSommet;
		nouveauSommet->precedent = temp;
		nbSommets++;
	}

	/*
	 * \fn Graphe::ajouterArc(const string&, const string&, float, float, int)
	 *
	 * \param[in] nom1: nom du sommet de départ
	 * \param[in] nom2: nom du sommet d'arrivée
	 * \param[in] duree: la duree pour traverser l'arc
	 * \param[in] cout: le coût pour traverser l'arc
	 * \param[in] ns: le niveau de sécurité de l'arc
	 */
	void Graphe::ajouterArc(const string& nom1, const string& nom2, float duree, float cout, int ns)
	{
		if(!sommetExiste(nom1) || !sommetExiste(nom2))
			throw logic_error("ajouterArc: un des noms passé en argument n'est pas dans le graphe");
		if(arcExiste(nom1, nom2))
			throw logic_error("ajouterArc: il y a déjà un arc orienté entre ces deux sommets");

		Sommet* depart = _getSommet(nom1);
		Sommet* arrivee = _getSommet(nom2);
		// pondération de l'arc qu'on ajoute au graphe
		Ponderations p;
		p.cout = cout;
		p.duree = duree;
		p.ns = ns;
		// arc qu'on va ajouter au graphe
		Arc* nouvArc = new Arc(arrivee, p);

		// cas premier arc du sommet depart
		if(depart->listeDest == NULL)
		{
			depart->listeDest = nouvArc;
			nbArcs++;
			return;
		}
		// sinon on va chercher l'avant-dernier arc dans la liste des arcs de depart
		Arc* temp = depart->listeDest;
		while(temp->suivDest != NULL)
			temp = temp->suivDest;
		temp->suivDest = nouvArc;
		nbArcs++;
	}

	/*
	 * \fn Graphe::enleverSommet()
	 *
	 * \param[in] nom: nom du sommet qu'on veut enlever du graphe
	 */
	void Graphe::enleverSommet(const string& nom)
	{
		if(!sommetExiste(nom))
			throw logic_error("enleverSommet: le sommet donné n'existe pas dans le graphe");
		// sommet temporaire qui pointera sur le sommet qu'on veut enlever
		Sommet* temp = _getSommet(nom);
		// on détruit tous les arcs sortant de ce sommet
		_detruireListeArc(temp->listeDest);
		temp->listeDest = NULL;
		// on enlève tous les arcs du graphe dont la destination est le sommet qu'on veut enlever
		_enleverArc(nom);
		// cas où on enlève le seul sommet du graphe
		if(nbSommets == 1)
		{
			delete listeSommets;
			listeSommets = NULL;
			nbSommets--;
			return;
		}
		// on réoriente le noeud précédent et le noeud suivant s'ils existent
		if(temp->precedent != NULL)
			temp->precedent->suivant = temp->suivant;
		if(temp->suivant != NULL)
			temp->suivant->precedent = temp->precedent;
		// si le noeud qu'on enlève est le premier de la liste on réoriente le pointeur listeSommets
		if(temp == listeSommets)
			listeSommets = temp->suivant;
		// On supprimer le noeud
		temp->suivant = temp->precedent = NULL;
		delete temp;
		nbSommets--;
	}

	/*
	 * \fn Graphe::enleverArc(const string&, const string&)
	 *
	 * \param[in] nom1: nom du sommet de départ de l'arc à enlever
	 * \param[in] nom2: nom du sommet d'arrivée de l'arc à enlever
	 */
	void Graphe::enleverArc(const string& nom1, const string& nom2)
	{
		if(!sommetExiste(nom1) || !sommetExiste(nom2))
			throw logic_error("enleverArc: un des noms passé en argument n'est pas dans le graphe");
		if(!arcExiste(nom1, nom2))
			throw logic_error("enleverArc: il n'y a pas d'arc entre le deux sommets passés en argument");

		Sommet* depart = _getSommet(nom1);
		Arc* temp = depart->listeDest;
		// si on doit enlever le premier arc de la liste
		if(temp->dest->nom == nom2)
		{
			depart->listeDest = temp->suivDest;
			temp->suivDest = NULL;
			delete temp;
			nbArcs--;
			return;
		}
		// sinon on va chercher l'arc précédent celui qu'on veut enlever
		while(temp->suivDest->dest->nom != nom2)
			temp = temp->suivDest;
		Arc* arcSupprimer = temp->suivDest;
		temp->suivDest = arcSupprimer->suivDest;
		arcSupprimer->suivDest = NULL;
		delete arcSupprimer;
		nbArcs--;
	}

	/**
	 * \fn Graphe::listerSommetsAdjacents(const string&) const
	 *
	 * \param [in] nom: nom du sommet qu'on recherche
	 *
	 * \return un vector<string> contenant le nom de tous les sommets adjacents au sommet qui a le nom nom
	 */
	vector<string> Graphe::listerSommetsAdjacents(const string& nom) const
	{
		if(!sommetExiste(nom))
			throw logic_error("listerSommetsAjacents: le nom passé en arguement correspond à aucun sommet du graphe");

		Sommet* temp = _getSommet(nom);
		Arc* tempArc = temp->listeDest;
		vector<string> sommetsAdjacents;
		while(tempArc != NULL)
		{
			sommetsAdjacents.push_back(tempArc->dest->nom);
			tempArc = tempArc->suivDest;
		}

		return sommetsAdjacents;
	}

	/*
	 * \fn Graphe::estVide() const
	 *
	 * \return true si le graphe est vide, false sinon
	 */
	bool Graphe::estVide() const
	{
		return nbSommets == 0;
	}

	/*
	 * \fn Graphe::nombreSommets() const
	 *
	 * \return renvoie le nombre de sommets dans le graphe
	 */
	int Graphe::nombreSommets() const
	{
		return nbSommets;
	}

	/*
	 * \fn Graphe::sommetExiste(const string&) const
	 *
	 * \param[in] nom: nom du sommet qu'on cherche dans le graphe
	 *
	 * \return true si le sommet est dans le graphe, false sinon
	 */
	bool Graphe::sommetExiste(const string& nom) const
	{
		Sommet* temp = listeSommets;
		while(temp != NULL)
		{
			if(temp->nom == nom)
				return true;
			temp = temp->suivant;
		}
		// le sommet n'est pas dans le graphe
		return false;
	}

	/*
	 * \fn Graphe::arcExiste(const string&, const string&)
	 *
	 * \param[in] sommetUn: sommet de départ de l'arc qu'on cherche
	 * \param[in] sommetDeux: sommet d'arrivée de l'arc qu'on cherche
	 *
	 * \return true si l'arc exist, false sinon
	 */
	bool Graphe::arcExiste(const string& sommetUn, const string& sommetDeux) const
	{
		if(!sommetExiste(sommetUn) || !sommetExiste(sommetDeux))
			throw logic_error("arcExist: l'un des deux sommets donnés en argument n'existe pas dans le graphe");

		Sommet* depart = _getSommet(sommetUn);
		Arc* temp = depart->listeDest;
		while(temp != NULL)
		{
			if(temp->dest->nom == sommetDeux)
				return true;
			temp = temp->suivDest;
		}
		return false;
	}

	/*
	 * \fn Graphe::detruireGraphe()
	 */
	void Graphe::detruireGraphe()
	{
		while(listeSommets != NULL)
			enleverSommet(listeSommets->nom);
	}

	/**
	 * \fn Graphe::getSommetEtat(const string&)
	 *
	 * \param [in] nom: nom du sommet recherché
	 *
	 * \return l'état du sommet
	 */
	bool Graphe::getSommetEtat(const string& nom) const
	{
		if(!sommetExiste(nom))
			throw logic_error("getSommetEtat: le nom passé en arguement correspond à aucun sommet du graphe");

		return (_getSommet(nom))->etat;
	}

	/**
	 * \fn Graphe::setSommetEtat(const string&, bool)
	 *
	 * \param [in] nom: nom de sommet qu'on recherche
	 * \param [in] etat: booléen qu'on veut assigner à l'attribut etat du sommet recherché
	 */
	void Graphe::setSommetEtat(const string& nom, bool etat)
	{
		if(!sommetExiste(nom))
			throw logic_error("setSommetEtat: le nom passé en arguement correspond à aucun sommet du graphe");

		(_getSommet(nom))->etat = etat;
	}

	/**
	 * \fn Graphe::setSommetFalse()
	 */
	void Graphe::setSommetsFalse()
	{
		Sommet* temp = listeSommets;
		while(temp != NULL)
		{
			temp->etat = false;
			temp = temp->suivant;
		}
	}

	/**
	 *  \fn Graphe::getNombreArcs()
	 *  \return un entier, le nombre d'arcs du graphe
	 */
	int Graphe::getNombreArcs() const
	{
		return nbArcs;
	}
	/**
	 *  \fn Graphe::listerNomsSommets()
	 *  \return un vecteur de string: chaque string est le nom d'un sommet
	 */
	std::vector<std::string> Graphe::listerNomsSommets() const
	{
		//creer le vector
		std::vector<std::string> nomsSommets;
		//faire le tour des sommets
		Sommet* sommetCourant = listeSommets;	//le premier sommet à traiter est celui pointé par listeSommets
		while(sommetCourant!=NULL)
		{
			//pour chaque sommet, on ajoute son nom au vector
			nomsSommets.push_back(sommetCourant->nom);
			//on incrémente sommetCourant
			sommetCourant = sommetCourant->suivant;
		}
		return nomsSommets;
	}


	/**
	 *  \fn Graphe::getPonderationsArc(const std::string& sommetUn, const std::string& sommetDeux)
	 *  \param[in] sommetUn et sommetDeux : les noms des sommets à chaque extrémité de l'arc
	 *  \return la Ponderation de l'arc
	 */
     Ponderations Graphe::getPonderationsArc(const std::string& sommetUn, const std::string& sommetDeux) const
     {
    	 try
    	 {
    		 if (!arcExiste(sommetUn, sommetDeux))
    			 throw logic_error("getPonderationsArc:  l'arc n'existe pas");
    	 }
    	 catch (logic_error& le)
    	 {
    		 throw le;
    	 }
    	 //rendu ici, l'arc existe
    	 //on retourne donc la ponderation
    	 return _getArc(sommetUn, sommetDeux)->ponder;

     }

     /**
	* \brief Retourne le nom d'un sommet selon ses coordonnées
	* \pre Le sommet doit faire partie du graphe
   * \post Le graphe reste inchangé.
	* \exception logic_error Le sommet n'existe pas
	*/
     /**
	 *  \fn Graphe::getNomSommet(float lt, float lg)
	 *  \param[in] lt: la latitude d'un sommet
	 *  \param[in] lg: la longitude d'un sommet
	 *  \return un string, le nom du sommet à ces coordonnées
	 */
	 std::string Graphe::getNomSommet(float lt, float lg) const
	 {

		 //on fait le tour des sommets
		 Sommet* sommetCourant = listeSommets;
		 Coordonnees coord;
		 coord.lg=lg;
		 coord.lt=lt;
		 string nomSommet;
		 while(sommetCourant!=NULL)
		 {
			 //on vérifie leur lg+lt
			 if (coord.lg==sommetCourant->coord.lg && coord.lt == sommetCourant->coord.lt)
			 {
				 //lorsqu'on trouve le bon sommet, on retourne son nom
				 return sommetCourant->nom;
			 }
			 //on incrémente sommetCourant
			 sommetCourant = sommetCourant->suivant;
		 }
		 //si on arrive à la fin et qu'on a rien trouvé, on lance un logic_error
		 throw logic_error("getNomSommet: le sommet n'existe pas.");
	 }


	 /**
	 *  \fn Graphe::getCoordonneesSommet(const std::string& nom)
	 *  \param[in] nom: le nom du sommet
	 *  \return les Coordonnees du sommet
	 */
	 Coordonnees Graphe::getCoordonneesSommet(const std::string& nom) const
	 {
		 if (nbSommets == 0)
			 throw logic_error("getCoordonnesSommet: il n'y a pas de sommets dans le graphe.");
		 if (!sommetExiste(nom))
			 throw logic_error("getCoordonnesSommet: le sommet n'existe pas.");
		 return _getSommet(nom)->coord;
	 }

	 /**
	 * \brief Obtenir une distance entre deux sommets.
	 * Cette fonction permet d'obtenir la distance entre deux sommets.
	 * \pre Les sommets doivent exister.
	 * \post Retourne la distance entre les sommets.
	 * \exception logic_error si un des sommets n'existe pas.
	 */
	 /**
	 *  \fn Graphe::getDistance(const std::string& sommetUn, const std::string& sommetDeux)
	 *  \param[in] sommetUn: le sommet de départ
	 *  \param[in] sommetDeux: le sommet d'arrivée
	 *  \return un float: la distance entre les deux sommets
	 */
	float Graphe::getDistance(const std::string& sommetUn, const std::string& sommetDeux) const
	{
		//si un des deux sommets n'existe pas, un lance une exception logic_error
		if (!sommetExiste(sommetUn) || !sommetExiste(sommetDeux))
			throw logic_error("getDistance: un des sommets spécifié n'existe pas.");

		float ltDepart = _getSommet(sommetUn)->coord.lt;
		float lgDepart = _getSommet(sommetUn)->coord.lg;
		float ltArrivee = _getSommet(sommetDeux)->coord.lt;
		float lgArrivee = _getSommet(sommetDeux)->coord.lg;
		return (float)sqrt( pow(ltArrivee-ltDepart , 2) + pow(lgArrivee-lgDepart , 2) );
	}





	/*
	 * \fn Graphe::_enleverArc(const string&)
	 *
	 * \param[in] nom: on supprime tous les arcs dont la destination est le sommet qui à ce nom
	 */
	void Graphe::_enleverArc(const string& nom)
	{
		// on parcourt tous les sommets du graphe
		Sommet* temp = listeSommets;
		while(temp != NULL)
		{
			if(temp->listeDest != NULL) // si le sommet à des arcs
			{
				// on parcourt tous les arcs du sommet courrant
				Arc* tempArc = temp->listeDest;
				if(tempArc->dest->nom == nom) // si le premier arc de la liste doit être supprimé
				{
					temp->listeDest = tempArc->suivDest;
					tempArc->suivDest = NULL;
					delete tempArc;
					nbArcs--;
					continue; // on peut passer au sommet suivant, un sommet n'aura pas deux arc qui vont à la même destination
				}
				Arc* next = tempArc->suivDest;
				while(next != NULL)
				{
					if(next->dest->nom == nom)
					{
						tempArc->suivDest = next->suivDest;
						next->suivDest = NULL;
						delete next;
						nbArcs--;
						break;
					}
					tempArc = next;
					next = next->suivDest;
				}
			}
			temp = temp->suivant;
		}
		return;
	}

	/*
	 * \fn Graphe::_detruireListeArc(Arc*)
	 *
	 * \param[in] l: pointeur sur le premier noeud de la liste à détruire
	 */
	void Graphe::_detruireListeArc(Arc* l)
	{
		if(l == NULL) // si la liste des destinations est vide on retourne sans lancer d'exception
			return;
		// sinon on détruit proprement chaque noeud de la liste
		Arc* temp = l;
		Arc* next = temp->suivDest;
		while(next != NULL)
		{
			temp->suivDest = NULL;
			delete temp;
			nbArcs--;
			temp = next;
			next = next->suivDest;
		}
		temp->suivDest = NULL;
		delete temp;
		nbArcs--;
	}

	/*
	 * \fn Graphe::_getSommet(const string& nom)
	 *
	 * \param[in] nom: nom du sommet qu'on cherche dans le graphe
	 *
	 * \return retourn un pointeur sur le sommet qui a le nom donné en argument
	 */
	Graphe::Sommet* Graphe::_getSommet(const string& nom) const
	{
		Sommet* temp =listeSommets;
		while(temp->nom != nom)
			temp = temp->suivant;
		return temp;
	}

	/**
	 *  \fn Graphe::_copieListeSommets(Sommet* listeSource, const int nbSommetsSource, const int nbArcsSource)
	 *  \param[in] listeSource - la liste à copier, nbSommetsSource - le nombre de sommets de la liste à copier, nbArcSource - le nombre
	 *  	d'arcs de la liste à copier
	 *  \return une liste de sommets qui est copie profonde de listeSource
	 */
	void Graphe::_copieListeSommets(Sommet* listeSource, const int nbSommetsSource, const int nbArcsSource)
	{
		nbSommets = 0;
		nbArcs=0;
		//il faut boucler dans liste sommets
		Sommet* premierSommet = NULL;
		Sommet* sommetPrecedent = NULL;
		Sommet* sommetSourceACopier = listeSource;
//		for (int i = 0; i < nbSommetsSource ; i++)

		while (sommetSourceACopier!=NULL)
		{
			//créer un nouveau sommet dans listeSommets avec tous les infos de listeSource[i]
			listeSommets = new Sommet(sommetSourceACopier->nom, sommetSourceACopier->coord);
			listeSommets->precedent = sommetPrecedent;

			if (listeSommets->precedent == NULL)
			{
				//si on traite le premier sommet, on met premierSommet sur le sommet qu'on vient de créer
				premierSommet = listeSommets;
			}
			else
			{
				//si ce n'est pas le premier sommet, le suivant du sommet precedent est ce sommet.
				listeSommets->precedent->suivant = listeSommets;
			}
			//on incrémente sommetPrecedent
			sommetPrecedent = listeSommets;
			//on incrémente listeSommets
			listeSommets = listeSommets->suivant;
			//on incrémente sommetSourceACopier
			sommetSourceACopier = sommetSourceACopier->suivant;
			//on incrémente nbSommets
			nbSommets++;
		}
		//on remet listeSommets sur le premier Sommet
		listeSommets = premierSommet;

		//maintenant que tous les sommets sont créés, on doit créer les arcs.
		//il faut boucler à travers les sommets et copier les arcs de la listeSource.
		Sommet * sommetCourant = premierSommet;
		Sommet * sommetSourceCourant = listeSource;
		while (sommetCourant != NULL)
		{
			Arc* arcSourceCourant = sommetSourceCourant->listeDest;
			if(arcSourceCourant != NULL)
			{
				sommetCourant->listeDest = new Arc(_getSommet(arcSourceCourant->dest->nom),arcSourceCourant->ponder);
				nbArcs++;
				arcSourceCourant = arcSourceCourant->suivDest;
			}
			Arc* arcCourant = sommetCourant->listeDest;
			while (arcSourceCourant!=NULL)
			{
				arcCourant->suivDest = new Arc(_getSommet(arcSourceCourant->dest->nom),arcSourceCourant->ponder);
				//on incrémente l'arc courant
				arcCourant = arcCourant->suivDest;
				//on incrémente l'arc source courant
				arcSourceCourant = arcSourceCourant->suivDest;
				//on incrémente le nombre d'arcs
				nbArcs++;
			}
			//on incrémente sommetCourant
			sommetCourant = sommetCourant->suivant;
			//on incrémente le sommetSourceCourant
			sommetSourceCourant = sommetSourceCourant->suivant;
		}
	}

	/**
	 *  \brief retourne un pointeur sur l'arc
	 *  \pre l'arc demandé existe
	 *  \post le pointeur retourné pointe sur l'arc avec les extrèmités sommetUn (départ) et sommetDeux (arrivé)
	 */
	/**
	 *  \fn Graphe::_getArc(const std::string& sommetUn, const std::string& sommetDeux)
	 *  \param[in] sommetUn: le sommet de départ de l'arc; sommetDeux: le sommet d'arrivée de l'arc
	 *  \return un pointeur sur l'arc demandé
	 */
	Graphe::Arc* Graphe::_getArc(const std::string& sommetUn, const std::string& sommetDeux) const
	{
		Sommet* sommetDepart = _getSommet(sommetUn);
		Sommet* sommetArrivee = _getSommet(sommetDeux);
		Arc* arcCourant = sommetDepart->listeDest;
		while(arcCourant->dest != sommetArrivee)
		{
			arcCourant = arcCourant->suivDest;
		}
		return arcCourant;
	}

} //Fin du namespace
